// max sum of any subarray in an array.

#include <iostream>
using namespace std;

int a[] = {4,-2,4,-5,-7,-3,2,-5,1,4,-2,4};
int s[1+sizeof(a)/sizeof(int)];
int p[1+sizeof(a)/sizeof(int)];
int msa(int i);

int main()
{
	s[0] = 0;
	int i = sizeof(a)/sizeof(int);
	s[0] = 0;
	int m = 0;
	msa(i);
	cout << "\n";
	int x;
	for(int j=1; j<=i; j++)
	{
		if(m<s[j])
		{
			m = s[j];
			x = p[j];
		}			
	}
	cout << "\nmax is : " << m << "::" << x << "\n";
	return 0;
}

int msa(int i)
{
	if(i==0)
	return 0;
	
	if(s[i])
	return s[i];
	s[i-1] = msa(i-1);
	s[i] = max(s[i-1]+a[i-1], a[i-1]);
	(s[i-1]+a[i-1] >= a[i-1])?(p[i]=p[i-1]):p[i]=i-1;
	return s[i];
}
		 
	 
